package day18;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/18 10:44
 */

/**
 * 给你一个正整数 n 。
 *
 * 请你将 n 的值替换为 n 的 质因数 之和，重复这一过程。
 *
 * 注意，如果 n 能够被某个质因数多次整除，则在求和时，应当包含这个质因数同样次数。
 * 返回 n 可以取到的最小值。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 15
 * 输出：5
 * 解释：最开始，n = 15 。
 * 15 = 3 * 5 ，所以 n 替换为 3 + 5 = 8 。
 * 8 = 2 * 2 * 2 ，所以 n 替换为 2 + 2 + 2 = 6 。
 * 6 = 2 * 3 ，所以 n 替换为 2 + 3 = 5 。
 * 5 是 n 可以取到的最小值。
 * 示例 2：
 *
 * 输入：n = 3
 * 输出：3
 * 解释：最开始，n = 3 。
 * 3 是 n 可以取到的最小值。
 */
public class Solution2 {
    public int smallestValue(int n) {
        while (true) {
            int sum = 0;
            int x = n;
            for (int i = 2; i * i <= x; i++)
                while (x % i == 0) {
                    sum += i;
                    x /= i;
                }
            if (x > 1)
                sum += x;
            if (sum == n)
                return n;
            n = sum;
        }
    }
}
